package com.sheng.leetcode.year2023.month01.day10;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * @author liusheng
 * @date 2023/01/10
 * <p>
 * 753. 破解保险箱<p>
 * <p>
 * 有一个需要密码才能打开的保险箱。密码是 n 位数, 密码的每一位是 k 位序列 0, 1, ..., k-1 中的一个 。<p>
 * 你可以随意输入密码，保险箱会自动记住最后 n 位输入，如果匹配，则能够打开保险箱。<p>
 * 举个例子，假设密码是 "345"，你可以输入 "012345" 来打开它，只是你输入了 6 个字符.<p>
 * 请返回一个能打开保险箱的最短字符串。<p>
 * <p>
 * 示例1:<p>
 * 输入: n = 1, k = 2<p>
 * 输出: "01"<p>
 * 说明: "10"也可以打开保险箱。<p>
 * <p>
 * 示例2:<p>
 * 输入: n = 2, k = 2<p>
 * 输出: "00110"<p>
 * 说明: "01100", "10011", "11001" 也能打开保险箱。<p>
 * <p>
 * 提示：<p>
 * n 的范围是 [1, 4]。<p>
 * k 的范围是 [1, 10]。<p>
 * k^n 最大可能为 4096。<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/cracking-the-safe">753. 破解保险箱</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0753 {

    @Test
    public void test01() {
//        int n = 1, k = 2;
        int n = 2, k = 2;
        System.out.println(new Solution().crackSafe(n, k));
    }
}

/**
 * n 的范围是 [1, 4]
 * k 的范围是 [1, 10]
 * k^n 最大可能为 4096
 */
class Solution {
    Set<Integer> seen = new HashSet<>();
    StringBuffer ans = new StringBuffer();
    int highest;
    int k;

    public String crackSafe(int n, int k) {
        /**
         * n = 1, k = 2: 说明密码只有一位数，可能是 0 ，也可能是 1，那么想要打开保险箱，输入必须为 "01" / "10"
         * n = 2, k = 2: 密码有两位，包含 "00" / "01" / "10"/ "11"，那么将这4种可能拼接起来，即 "00110" / "01100" / "10011" / "11001" 这几个字符串是包含所有密码的最短字符串
         */
        highest = (int) Math.pow(10, n - 1);
        this.k = k;
        dfs(0);
        for (int i = 1; i < n; i++) {
            ans.append('0');
        }
        return ans.toString();
    }

    public void dfs(int node) {
        for (int x = 0; x < k; ++x) {
            int nei = node * 10 + x;
            if (!seen.contains(nei)) {
                seen.add(nei);
                dfs(nei % highest);
                ans.append(x);
            }
        }
    }
}

//class Solution {
//public:
//    string crackSafe(int n, int k) {
//        int kn = pow(k, n), kn_1 = pow(k, n-1);//将所有n-1位数作为节点的节点个数
//        vector<int> num(kn_1,k-1);//表示k^(n-1)个节点的下一位可以从k-1选到0，当前索引处对应的元素值表示该节点已经把比元素值大的值都作为下一数字添加过了
//        string s(kn + (n-1), '0');//字符串初始化，（结果一定是kn+n-1位）
//        for(int i = n-1, node = 0; i < s.size(); ++i) {//i从n-1开始递增 （第一个密码是n-1个0（00...为起始点））
//            s[i] = num[node]-- + '0';//更新字符串。先运算 再--，表示下一次该节点要选的下一数字
//            node = node*k - (s[i-(n-1)]-'0')*kn_1 + num[node] + 1;//更新当前节点。
//            //左移操作：1.*k,2.减去左侧超出的一位代表的数字（这位数字已经到了k^(n-1)上，所以后面×一个k(n-1)）,3.加上右边进来的新数字(刚才-1用于下次的选路径，但这次的节点还没更新呢，要把这个1加回来)
//        }
//        return s;
//    }
//};
